package tree.threadedTree;

import lombok.Data;

/**
 * @author： pang-yun
 * @date： 2021-11-03 16:16
 * 功能目的 ：用于  线索化二叉树
 */

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        Node root = new Node(1, "tom");
        Node nodeA = new Node(3, "jack");
        Node nodeB = new Node(6, "smith");
        Node nodeC = new Node(8, "mary");
        Node nodeD = new Node(10, "king");
        Node nodeE = new Node(14, "dim");

        // 手动创建
        root.setLeftNode(nodeA);
        root.setRightNode(nodeB);
        nodeA.setLeftNode(nodeC);
        nodeA.setRightNode(nodeD);
        nodeB.setLeftNode(nodeE);

        //线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();

        System.out.println(nodeD.getLeftNode());
        System.out.println(nodeD.getRightNode());

    }
}

// 定义 线索化 二叉树
@Data
class ThreadedBinaryTree {
    private Node root;

    // 为了实现线索化 需要创建给 当前节点 的 前驱节点的指针
    // 在递归线索化 时 ，pre 总是 保留 前一个节点
    private Node pre = null;

    public void threadedNodes(){
        this.threadedNodes(root);
    }

    //  编写 对二叉树 进行中序线索化的方法
    public void threadedNodes(Node node) {
        // 如果 node == null 不能线索化
        if (node == null) {
            return;
        }
        //线索化 左子树
        threadedNodes(node.getLeftNode());

        // 线索化 当前节点

        // 处理当前节点的 前驱节点
        if (node.getLeftNode() == null) {
            // 让当前节点的左指针 指向前驱节点
            node.setLeftNode(pre);
            // 修改类型
            node.setLeftType(1);
        }

        //处理后续节点
        if (pre != null && pre.getRightNode() == null) {
            // 前驱节点的 右指针指向 当前节点
            pre.setRightNode(node);
            // 修改前驱结点的 右指针类型
            pre.setRightType(1);
        }
        //!!! 每处理一个节点后  让当前节点 是 下一个节点的前驱结点
        pre = node;


        // 线索化 右子树
        threadedNodes(node.getRightNode());
    }


    // 删除节点
    public void deleteNode(int no) {
        if (root != null) {
            // 递归删除
            root.deleteNode(no);
        } else {
            System.out.println("BinaryTree 为空树！");
        }
    }


    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    // 后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
}


// 单个节点
@Data
class Node {
    private int id;
    private String name;
    private Node leftNode;
    private Node rightNode;
    //0  指向的是 左子树   1 指向的是 前驱结点
    private int leftType;
    //0 指向的是  右子树  1 指向的是  后驱节点
    private int rightType;


    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    // 删除节点
    public void deleteNode(int no) {
        // 如果当前 节点 的左子节点 不为空,并且左子节点就是要删除的  就将 this.leftNode = null
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        // 如果当前 节点 的右子节点 不为空,并且右子节点就是要删除的  就将 this.rightNode = null
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        // 向左子树 递归遍历
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }
        // 向右子树 递归遍历
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }


    // 前序遍历    先输出父节点  然后左节点  右节点
    public void preOrder() {
        System.out.println(this);
        // 递归向左子树前序遍历
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        // 递归向柚子树前序遍历
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }

    // 中序遍历  先输出左节点   再输出父节点  最后输出 右节点
    public void infixOrder() {
        //递归向左子树遍历
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        //递归向右子树遍历
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }

    // 后序遍历  先遍历左节点  再遍历右节点  最后输出父节点
    public void postOrder() {
        //递归向左子树遍历
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        // 递归向右子树遍历
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
}